package weekMatch.one_350;

import node.Node;

public class LeeCode_03_02 {
    public static void main(String[] args) {
//        System.out.println(specialPerm(new int[]{2, 3, 6}));
//        System.out.println(specialPerm(new int[]{1,4,3}));
//        System.out.println(specialPerm(new int[]{31,93}));
        System.out.println(specialPerm(new int[]{1,2}));
        System.out.println(specialPerm(new int[]{1,1,1,1,1,1,1,1,1,1,1,1,1,1}));
//        System.out.println(specialPerm(new int[]{20,100,50,5,10,70,7}));
//        System.out.println(specialPerm(new int[]{1,1,1}));
    }
    private static int specialPerm(int[] nums) {
        int n = nums.length;
        long[][] dp = new long[1 << n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0){
                    int index = (1 << i) | (1 << j);
                    dp[index][i] = 1;
                    dp[index][j] = 1;
                }
            }
        }
        int max = 1 << n;
        return (int) dfs(dp, max - 1, -1);
    }
    private static long dfs(long[][] dp, int now, int pre){
        if (now == 0)
            return 1;
        if (pre != -1 && dp[now][pre] > 0)
            return dp[now][pre];
        long res = 0;
        long mod = (long) (1e9 + 7);
        int n = dp[0].length;
        for (int i = 0; i < n; i++) {
            if ((now & (1 << i)) != 0){
                if (pre == -1) {
                    res += dfs(dp, now ^ (1 << i), i);
                    res %= mod;
                }else if (dp[(1 << i) | (1 << pre)][i] != 0){
                    res += dfs(dp, now ^ (1 << i), i);
                    res %= mod;
                }
            }
        }
        pre = pre == -1 ? 0 : pre;
        dp[now][pre] = res;
        return res;
    }
}